package 剑指Offer;

import com.sun.org.apache.xpath.internal.operations.Variable;

public class Offer53I_在排序数组中查找数字I {

    int count = 0;

    public static void main(String[] args) {
        System.out.println(new Offer53I_在排序数组中查找数字I().search(new int[]{5, 7, 7, 8, 8, 10}, 8));
    }

    public int search(int[] nums, int target) {
        int find = Helper(nums, target);
        //如果没找到，返回0
        if (find == -1) {
            return 0;
        }

        int left = find - 1;
        int right = find + 1;
        //查看前面是否还有target
        while (left >= 0 && nums[left] == target) {
            left--;
        }
        //查看后面是否还有target
        while (right < nums.length && nums[right] == target) {
            right++;
        }

        return (right - 1) - (left + 1) + 1;
    }

    //二分法查找
    public int Helper(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
                /*找到了该目标值的地址，就将地址返回，但是要注意，再寻找一下还有没有其余的target*/
            }
        }
        return -1;//如果没找到就返回-1
    }
}
